home *** CD-ROM | disk | FTP | other *** search
RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) NNNNaaaammmmeeee RWBTreeOnDisk - Rogue Wave library class SSSSyyyynnnnooooppppssssiiiissss typedef long RWstoredValue ; typedef int (*RWdiskTreeCompare)(const char*, const char*, size_t); #include <rw/disktree.h> #include <rw/filemgr.h> RWFileManager fm("filename.dat"); RWBTreeOnDisk bt(fm); DDDDeeeessssccccrrrriiiippppttttiiiioooonnnn Class RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk represents an ordered collection of associations of keys and values, where the ordering is determined by comparing keys using an external function. The user can set this function. Duplicate keys are not allowed. Given a key, the corresponding value can be found. This class is specifically designed for managing a B-tree in a disk file. Keys, defined to be arrays of cccchhhhaaaarrrrssss, and values, defined by the typedef RRRRWWWWssssttttoooorrrreeeeddddVVVVaaaalllluuuueeee, are stored and retrieved from a B-tree. The values can represent offsets to locations in a file where objects are stored. The key length is set by the constructor. By default, this value is 16 characters. By default, keys are null-terminated. However, the tree can be used with embedded nulls, allowing multibyte and binary data to be used as keys. To do so you must: Specify TTTTRRRRUUUUEEEE for parameter iiiiggggnnnnoooorrrreeeeNNNNuuuullllllll in the constructor (see below); Make sure all buffers used for keys are at least as long as the key length (remember, storage and comparison will nnnnooootttt stop with a null value); Use a comparison function (such as mmmmeeeemmmmccccmmmmpppp(((())))) that ignores nulls. This class is meant to be used with class RRRRWWWWFFFFiiiilllleeeeMMMMaaaannnnaaaaggggeeeerrrr which manages the allocation and deallocation of space in a disk file. When you construct an RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk you give the location of the root node in the constructor as argument ssssttttaaaarrrrtttt. If this value is RRRRWWWWNNNNIIIILLLL (the default) then the location will be retrieved from the RRRRWWWWFFFFiiiilllleeeeMMMMaaaannnnaaaaggggeeeerrrr using function ssssttttaaaarrrrtttt(((()))) (see class RRRRWWWWFFFFiiiilllleeeeMMMMaaaannnnaaaaggggeeeerrrr). You can also use the enumeration ccccrrrreeeeaaaatttteeeeMMMMooooddddeeee to set whether to use an existing tree (creating one if one doesn't exist) or to force the creation of a new tree. The location of the resultant root node can be retrieved using member function bbbbaaaasssseeeeLLLLooooccccaaaattttiiiioooonnnn(((()))).... More than one B-tree can exist in a disk file. Each must have its own separate root node. This can be done by constructing more than one RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk, each with ccccrrrreeeeaaaatttteeeeMMMMooooddddeeee set to ccccrrrreeeeaaaatttteeee. The PPPPaaaaggggeeee 1111 RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) oooorrrrddddeeeerrrr of the B-tree can be set in the constructor. Larger values will result in shallower trees, but less efficient use of disk space. The minimum number of entries in a node can also be set. Smaller values may result in less time spent balancing the tree, but less efficient use of disk space. PPPPeeeerrrrssssiiiisssstttteeeennnncccceeee None EEEEnnnnuuuummmmeeeerrrraaaattttiiiioooonnnnssss enum styleMode {V6Style, V5Style}; This enumeration is used by the constructor to allow backwards compatibility with older V5.X style trees, which supported only 16-byte key lengths. It is used only when creating a new tree. If opening a tree for update, its type is determined automatically at runtime. VVVV6666SSSSttttyyyylllleeee Initialize a new tree using V6.X style trees. This is the default. VVVV5555SSSSttttyyyylllleeee Initialize a new tree using V5.X style trees. In this case, the key length is fixed at 16 bytes. enum createMode {autoCreate, create}; This enumeration is used by the constructor to determine whether to force the creation of a new tree. aaaauuuuttttooooCCCCrrrreeeeaaaatttteeee Look in the location given by the constructor argument ssssttttaaaarrrrtttt for the root node. If valid, use it. Otherwise, allocate a new tree. This is the default. ccccrrrreeeeaaaatttteeee Forces the creation of a new tree. The argument ssssttttaaaarrrrtttt is ignored. PPPPuuuubbbblllliiiicccc CCCCoooonnnnssssttttrrrruuuuccccttttoooorrrr RWBTreeOnDisk(RWFileManager& f, unsigned nbuf = 10, createMode omode = autoCreate, unsigned keylen = 16, RWBoolean ignoreNull = FALSE, RWoffset start = RWNIL, styleMode smode = V6Style, unsigned halfOrder = 10, unsigned minFill = 10); Construct a B-tree on disk. The parameters are as follows: ffff The file in which the B-tree is to be managed. This is the only required parameter. PPPPaaaaggggeeee 2222 RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) nnnnbbbbuuuuffff The maximum number of nodes that can be cached in memory. oooommmmooooddddeeee Determines whether to force the creation of a new tree or whether to attempt to open an existing tree for update (the default). kkkkeeeeyyyylllleeeennnn The length of a key in bytes. Ignored when opening an existing tree. iiiiggggnnnnoooorrrreeeeNNNNuuuullllllll Controls whether to allow embedded nulls in keys. If FFFFAAAALLLLSSSSEEEE (the default), then keys end with a terminating null. If TTTTRRRRUUUUEEEE, then all kkkkeeeeyyyylllleeeennnn bytes are significant. Ignored when opening an existing tree. ssssttttaaaarrrrtttt Where to find the root node. If set to RRRRWWWWNNNNIIIILLLL (the default), then uses the value returned by the RRRRWWWWFFFFiiiilllleeeeMMMMaaaannnnaaaaggggeeeerrrr''''ssss ssssttttaaaarrrrtttt(((()))) member function. Ignored when creating a new tree. ssssmmmmooooddddeeee Sets the type of B-tree to create, allowing backwards compatibility (see above). The default specifies new V6.X style B-trees. Ignored when opening an existing tree. hhhhaaaallllffffOOOOrrrrddddeeeerrrr One half the order of the B-tree (that is, one half the number of entries in a node). Ignored when opening an existing tree. mmmmiiiinnnnFFFFiiiillllllll The minimum number of entries allowed in a node (must be less than or equal to hhhhaaaallllffffOOOOrrrrddddeeeerrrr). Ignored when opening an existing tree. PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr FFFFuuuunnnnccccttttiiiioooonnnnssss void aaaappppppppllllyyyyTTTTooooKKKKeeeeyyyyAAAAnnnnddddVVVVaaaalllluuuueeee((*ap)(const char*,RWstoredValue), void* x); Visits all items in the collection in order, from smallest to largest, calling the user-provided function pointed to by aaaapppp with the key and value as arguments. This function should have the prototype: void yyyyoooouuuurrrrAAAAppppppppllllyyyyFFFFuuuunnnnccccttttiiiioooonnnn(const char* ky, RWstoredValue val,void* x); The function yyyyoooouuuurrrrAAAAppppppppllllyyyyFFFFuuuunnnnccccttttiiiioooonnnn mmmmaaaayyyy nnnnooootttt change the key. The value xxxx can be anything and is passed through from the call to aaaappppppppllllyyyyTTTTooooKKKKeeeeyyyyAAAAnnnnddddVVVVaaaalllluuuueeee(((()))). This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. RWoffset bbbbaaaasssseeeeLLLLooooccccaaaattttiiiioooonnnn() const; Returns the offset of this tree's starting location within the RRRRWWWWFFFFiiiilllleeeeMMMMaaaannnnaaaaggggeeeerrrr. This is the value you will pass to a constructor as the PPPPaaaaggggeeee 3333 RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) ssssttttaaaarrrrtttt argument when you want to open one of several trees stored in one managed file. unsigned ccccaaaacccchhhheeeeCCCCoooouuuunnnntttt() const; Returns the maximum number of nodes that may currently be cached. unsigned ccccaaaacccchhhheeeeCCCCoooouuuunnnntttt(unsigned newcount); Sets the number of nodes that should be cached to nnnneeeewwwwccccoooouuuunnnntttt. Returns the old number. void cccclllleeeeaaaarrrr(); Removes all items from the collection.This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. RWBoolean ccccoooonnnnttttaaaaiiiinnnnssss(const char* ky) const; Returns TTTTRRRRUUUUEEEE if the tree contains a key that is equal to the string pointed to by kkkkyyyy, and FFFFAAAALLLLSSSSEEEE otherwise. This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. size_t eeeennnnttttrrrriiiieeeessss(); Returns the number of items in the RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk. This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. RWoffset eeeexxxxttttrrrraaaaLLLLooooccccaaaattttiiiioooonnnn(RWoffset newlocation); Sets the location where this RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk keeps your own application- specific information to nnnneeeewwwwllllooooccccaaaattttiiiioooonnnn. Returns the previous value. RWBoolean ffffiiiinnnnddddKKKKeeeeyyyy( const char* ky, RWCString& foundKy)const ; Returns TTTTRRRRUUUUEEEE if kkkkyyyy is found, otherwise FFFFAAAALLLLSSSSEEEE.... If successful, the found key is returned as a reference in ffffoooouuuunnnnddddKKKKyyyy. This member function may throw PPPPaaaaggggeeee 4444 RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. RWBoolean ffffiiiinnnnddddKKKKeeeeyyyyAAAAnnnnddddVVVVaaaalllluuuueeee( const char* ky, RWCString& foundKy, RWStoredValue& foundVal)const ; Returns TTTTRRRRUUUUEEEE if kkkkyyyy is found, otherwise FFFFAAAALLLLSSSSEEEE.... If successful, the found key is returned as a reference in ffffoooouuuunnnnddddKKKKyyyy, and the value is returned as a reference in ffffoooouuuunnnnddddVVVVaaaallll. This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. RWstoredValue ffffiiiinnnnddddVVVVaaaalllluuuueeee(const char* ky)const; Returns the value for the key that compares equal to the string pointed to by kkkkyyyy. Returns RRRRWWWWNNNNIIIILLLL if no key is found. This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. int hhhheeeeiiiigggghhhhtttt(); Returns the height of the RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk. A possible exception is RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr. int iiiinnnnsssseeeerrrrttttKKKKeeeeyyyyAAAAnnnnddddVVVVaaaalllluuuueeee(const char* ky,RWstoredValue v); Adds a key-value pair to the B-tree. Returns TTTTRRRRUUUUEEEE for successful insertion, FFFFAAAALLLLSSSSEEEE otherwise. A possible exception is RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr. unsigned kkkkeeeeyyyyLLLLeeeennnnggggtttthhhh() const; Return the length of the keys for this RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk. This number is set when the tree is first constructed and cannot be changed. unsigned mmmmiiiinnnnOOOOrrrrddddeeeerrrr()const; Return the minimum number of items that may be found in any non-root node in this RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk. This number is set when the tree is first constructed and cannot be changed. PPPPaaaaggggeeee 5555 RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) unsigned nnnnooooddddeeeeSSSSiiiizzzzeeee() const; Returns the number of bytes used by each node of this RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk. This number is calculated from the length of the keys and the order of the tree, and cannot be changed. We make it available to you for your calculations about how many nodes to cache. unsigned oooorrrrddddeeeerrrr()const; Return half the maximum number of items that may be stored in any node in this RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk. This number is set when the tree is first constructed and cannot be changed. This method should have been renamed "hhhhaaaallllffffOOOOrrrrddddeeeerrrr" but is still called "oooorrrrddddeeeerrrr" for backward compatibility. RWBoolean iiiissssEEEEmmmmppppttttyyyy() const; Returns TTTTRRRRUUUUEEEE if the RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk is empty, otherwise FFFFAAAALLLLSSSSEEEE. void rrrreeeemmmmoooovvvveeee(const char* ky); Removes the key and value pair that has a key which matches kkkkyyyy. This member function may throw an RRRRWWWWFFFFiiiilllleeeeEEEErrrrrrrr exception. RWBoolean rrrreeeeppppllllaaaacccceeeeVVVVaaaalllluuuueeee(const RWCString& key, const RWstoredValue newval, RWstoredValue& oldVal); Attempts to replace the RRRRWWWWssssttttoooorrrreeeeddddVVVVaaaalllluuuueeee now associated with kkkkeeeeyyyy by the value nnnneeeewwwwvvvvaaaallll. If successful, the previous value is returned by reference in oooollllddddVVVVaaaallll; and the methed returns TTTTRRRRUUUUEEEE. Otherwise, returns FFFFAAAALLLLSSSSEEEE. RWdiskTreeCompare sssseeeettttCCCCoooommmmppppaaaarrrriiiissssoooonnnn(RWdiskTreeCompare fun); Changes the comparison function to ffffuuuunnnn and returns the old function. This function must have prototype: int yyyyoooouuuurrrrFFFFuuuunnnn(const char* key1, const char* key2, size_t N); PPPPaaaaggggeeee 6666 RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) RRRRWWWWBBBBTTTTrrrreeeeeeeeOOOOnnnnDDDDiiiisssskkkk((((3333CCCC++++++++)))) It should return a number less than zero, equal to zero, or greater than zero depending on whether the first argument is less than, equal to or greater than the second argument, respectively. The third argument is the key length. Possible choices (among others) are ssssttttrrrrnnnnccccmmmmpppp(((()))) (the default), or ssssttttrrrrnnnniiiiccccmmmmpppp(((()))) (for case-independent comparisons). PPPPaaaaggggeeee 7777 
